/**
 * https://leetcode.cn/submissions/detail/585053586/
 * 1376. 通知所有员工所需的时间
 * Medium, 黄伟杰 2024.12.04
 * DFS
 */

class Solution
{
public:
    int numOfMinutes(int n, int headID, vector<int> &manager, vector<int> &informTime)
    {
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++)
            if (manager[i] >= 0)
                g[manager[i]].push_back(i); // 树
        auto dfs = [&](auto dfs, int x) -> int
        {
            int maxn = 0;
            for (int y : g[x])
                maxn = max(maxn, dfs(dfs, y));
            return maxn + informTime[x];
        };
        return dfs(dfs, headID);
    }
};